package org.example;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.function.Consumer;

/**
 * @Author xhw
 * @Date 2023/11/7
 * @Version 1.0
 */
class Tree {
    //定义了一个根节点
    public TreeNode root;

    //广度遍历
    public void breadthFirstSearch() {
        if (root == null) {
            System.out.println("树是空的，没有内容");
        } else {
            //获取最大深度
            int height = getHeight(root);
            for (int i = 1; i <= height; i++) {
                printLevel(root, i);
                System.out.println(); // 在每一层结束后换行
            }

        }
    }

    //深度优先搜索
    public void depthFirstSearch(TreeNode node) {
        if (node != null) {
            // 打印当前节点的值
            System.out.print(node.getVal() + " ");
            for (TreeNode child : (List<TreeNode>) node.getChildren()) {
                // 递归遍历子节点
                depthFirstSearch(child);
            }
        }
    }

    //使用递归删除节点
    public void delete(int val) {
        //一层一层删，就判断当前层是空能不能删，首先进行一个根节点是不是空如果没有就提示为空
        if (root == null) {
            System.out.println("树是空的，没有内容");
            //再进行判断，如果有当前层的值和匹配的那就是根节点，直接删除，否则是子节点那就调用删除的具体方法deleteNode
        } else if (root.getVal().equals(val)) {
            root = null;
        } else {
            deleteNode(root, val);
        }
    }


    //插入树节点，传入父节点的值和新节点的值
    public void insert(int parentVal, int val) {
        //创建一个新的节点也就是要插入的树节点
        TreeNode newNode = new TreeNode(val);
        //如果root为空那就是根节点那就把parentval设置为树节点然后新增为他的子节点
        if (root == null) {
            root = new TreeNode(parentVal);
            root.getChildren().add(newNode);
        } else {
            //否则是普通节点那就先查询，查询到父节点的值，找到了就插入，没找到就返回一个没找到的提示
            TreeNode parentNode = findNode(root, parentVal);
            if (parentNode != null) {
                parentNode.getChildren().add(newNode);
            } else {
                System.out.println("没有该值");
            }
        }

    }

    //删除具体方法
    private void deleteNode(TreeNode node, int val) {
        //让当前的节点的子节点遍历然后判断val值是不是相等相等就直接使用remove删除
        for (TreeNode child : (List<TreeNode>) node.getChildren()) {
            if (child.getVal().equals(val)) {
                node.getChildren().remove(child);
                return;
            } else {
                //如果没有找到说明可能再更深的子树节点里面，可以把子节点传入再调用本身
                deleteNode(child, val);
            }
        }
    }

    //查找节点，传入一个当前节点用来输出，一个是要找的值（深度递归）
    private TreeNode findNode(TreeNode node, int val) {
        //先判断当前节点是不是要找的值，是就可以直接返回（第一层）
        if (node.getVal().equals(val)) {
            return node;
        }
        //不是的话就遍历找到的所有当前子节点的列表，也就是一直调用第一层的方法，找到了就返回一个对象，没找到就返回提示没有该值（第n层）
        for (TreeNode child : (List<TreeNode>) node.getChildren()) {
            TreeNode foundNode = findNode(child, val);
            if (foundNode != null) {
                return foundNode;
            }
        }
        return null;
    }

    //获取最大深度
    private int getHeight(TreeNode node) {
        //如果传入的节点为空，即树为空，那么深度为0
        if (node == null) {
            return 0;
            //定义一个变量 maxChildHeight，用于记录子节点的最大深度
        } else {
            int maxChildHeight = 0;
            //依次取出每个子节点。
            for (TreeNode child : (List<TreeNode>) node.getChildren()) {
                //递归地计算子节点的深度
                int childHeight = getHeight(child);
                //取所有子节点中深度的最大值
                maxChildHeight = Math.max(maxChildHeight, childHeight);
            }
            return 1 + maxChildHeight;
        }
    }

    //按照获取到的深度level进行打印
    private void printLevel(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        //如果当前层级为1，那么就可以直接打印
        if (level == 1) {
            System.out.print(node.getVal() + " ");
            //大于1就是说明还有子树，那么就可以获取之后再进行打印然后层级-1
        } else if (level > 1) {
            for (TreeNode child : (List<TreeNode>) node.getChildren()) {
                printLevel(child, level - 1);
            }
        }
    }

    //深度迭代
    public void deep(final TreeNode node, final Consumer<TreeNode> consumer) {
        consumer.accept(node);

        for (TreeNode child : (List<TreeNode>) node.getChildren()) {
            deep(child, consumer);
        }

    }

    //广度迭代
    public void breadth(final TreeNode root, final Consumer<TreeNode> consumer) {
        List<TreeNode> currentLevel = new ArrayList<>();
        currentLevel.add(root);
        while (!currentLevel.isEmpty()) {
            List<TreeNode> nextLevel = new ArrayList<>();
            for (TreeNode node : currentLevel) {
                consumer.accept(node);
                nextLevel.addAll(node.getChildren());
            }
            currentLevel = nextLevel; // 更新currentLevel为下一层的节点列表
        }
    }
}

